package com.sjf.day02.linkedlist;

/**
 * 约瑟夫问题
 *
 * @author <huangtang>
 * @since 2021/12/22 11:02
 **/
public class Josepfu {

    public static void main(String[] args) {
        CircleSingleLinkedList linkedList = new CircleSingleLinkedList();
        linkedList.add(25);
        //linkedList.list();
        linkedList.countBoy(1,2,50);
    }


}
//创建一个单向环形链表
class CircleSingleLinkedList{
    private Boy first = null; //创建一个头节点

    /**
     * 遍历环形链表
     */
    public void list(){
        //判断链表是否为空
        if(first == null){
            System.out.println("链表为空");
            return;
        }
        //因为first不能动，创建一个辅助指针
        Boy curBoy = first;
        while(true){
            System.out.println("小孩的编号:"+curBoy.no);
            if(curBoy.next==first){
                //遍历完成
                break;
            }
            curBoy = curBoy.next;//curBoy指针后移遍历
        }
    }

    /**
     * 添加节点方法
     */
    public void add (int nums){
        if(nums < 1){
            System.out.println("nums值 不正确");
            return;
        }
        Boy curBoy = null; //辅助指针，遍历链表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建节点
            Boy boy = new Boy(i);
            //如果是第一个节点
            if(i == 1){
                first = boy;
                first.next = boy;
                curBoy = first;
            }else{
                //不是第一个节点，新加入的节点
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
            }


        }
    }

    /**
     * 开始出圈
     * @param startNo 从第几个开始数
     * @param countNum 数几个数出圈
     * @param nums  总共有几个节点参与
     */
    public void countBoy(int startNo,int countNum,int nums){
        //先对数据进行校验
        if(first==null || startNo < 1||startNo>nums){
            System.out.println("参数错误");
            return;
        }
        //创建辅助节点，用于删除节点
        Boy temp = first;
        //遍历链表，让辅助节点temp指向first的前一个结点
        while(true){
            if(temp.next == first){
                //temp指向最后一个节点
                break;
            }
            temp = temp.next;
        }
        //报数时，让first和temp指针都移动startNo-1，移动到指定开始位置
        for(int i=0;i<startNo-1;i++){
            first = first.next;
            temp = temp.next;
        }
        //开始报数，让temp和first都移动countNum-1次，然后出圈
        while(true){
            //循环知道temp和first都指向一个节点时结束
            if(first == temp){
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                temp = temp.next;
            }
            //此时小孩出圈
            System.out.printf("小孩%d出圈\n",first.no);
            first = first.next;
            temp.next = first; //删除对应节点
        }
        System.out.println("最后留在圈里的节点时"+first.no);
    }

}

//定义节点
class Boy{
    public int no;
    public Boy next;
    public Boy(int no){
        this.no = no;
    }


}
